package com.kevin.Code.DP;

/**
 * @author Vinlee Xiao
 * @Classname MaximalSquare
 * @Description Leetcode 221 最大正方形 中等难度 动态规划 没思路
 * @Date 2021/10/8 20:34
 * @Version 1.0
 */
public class MaximalSquare {

    /**
     * 方法一：暴力法 思路明了 容易理解
     *
     * @param matrix
     * @return
     */
    public int maximalSquare(char[][] matrix) {


        int row = matrix.length;
        int col = matrix[0].length;

        int maxSide = 0;

        //以matrix
        for (int i = 0; i < row; i++) {
            for (int j = 0; j < col; j++) {
                if (matrix[i][j] == '1') {

                    maxSide = Math.max(maxSide, 1);
                    //向下遍历的最小的长度
                    int minSide = Math.min(row - i, col - j);
                    //以matrix[i][j]作为左上角坐标 开始沿x y轴遍历 对角线遍历

                    for (int index = 1; index < minSide; index++) {

                        boolean flag = true;
                        //对角线
                        if (matrix[i + index][j + index] == '0') {
                            break;
                        }

                        //对一行列的数据进行遍历 看是否符合要求
                        for (int k = 0; k < index; k++) {
                            //先对一行的数据进行遍历  再对一列的数据进行遍历
                            if (matrix[i + index][j + k] == '0' || matrix[i + k][j + index] == '0') {
                                //
                                flag = false;
                                break;
                            }

                        }
                        if (flag) {
                            maxSide = Math.max(maxSide, index + 1);
                        } else {
                            break;
                        }


                    }
                }
            }
        }

        int maxSquare = maxSide * maxSide;
        return maxSquare;
    }


    /**
     * 动态规划 没想到思路
     *
     * @param matrix
     * @return
     */
    public int maximalSquare1(char[][] matrix) {


        int row = matrix.length;
        int col = matrix[0].length;

        int maxSide = 0;
        //明确dp数组的含义dp[i][j] 指以坐标i，j为右下角的坐标的 含有的最大边长
        int[][] dp = new int[row + 1][col + 1];

        for (int i = 1; i <= row; i++) {
            for (int j = 1; j <= col; j++) {

                if (matrix[i - 1][j - 1] == '1') {
                    //边界情况 第一行 第一列的数据 为边长1
                    if (i - 1 == 0 || j - 1 == 0) {
                        dp[i][j] = 1;
                    } else {
                        //当前坐标的只取决于当前坐标上下左右的坐标的最小值
                        dp[i][j] = Math.min(dp[i - 1][j - 1], Math.min(dp[i - 1][j], dp[i][j - 1])) + 1;
                    }
                    maxSide = Math.max(maxSide, dp[i][j]);
                }


            }

        }


        return maxSide * maxSide;
    }


    public static void main(String[] args) {
        MaximalSquare maximalSquare = new MaximalSquare();


//        maximalSquare.maximalSquare();

    }
}
